package problem.year2021.february;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。
 * <p>
 * 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
 * 示例 1：
 * <p>
 * 输入：[1, 2, 2, 3, 1]
 * 输出：2
 * 解释：
 * 输入数组的度是2，因为元素1和2的出现频数最大，均为2.
 * 连续子数组里面拥有相同度的有如下所示:
 * [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
 * 最短连续子数组[2, 2]的长度为2，所以返回2.
 * <p>
 * 示例 2：
 * <p>
 * 输入：[1,2,2,3,1,4,2]
 * 输出：6
 * 提示：
 * nums.length 在1到 50,000 区间范围内。
 * nums[i] 是一个在 0 到 49,999 范围内的整数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/degree-of-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class February20 {
    /**
     * 第一步：先找出数组的度数
     * 第二步：滑动窗口利用度数找出其字串长度
     *
     * @param nums 输入数组
     * @return 返回字串长度
     */
    public int findShortestSubArray(int[] nums) {
        int len = nums.length;
        Map<Integer, int[]> map = new HashMap<>();
        // int[] 为3列数组，第一个表示其出现次数，第二个表示其开始位置，第三个表示其结尾位置
        for (int i = 0; i < len; ++i) {
            if (map.containsKey(nums[i])) {
                map.get(nums[i])[0]++;
                map.get(nums[i])[2] = i;
            } else {
                map.put(nums[i], new int[]{1, i, i});
            }
        }
        int maxnum = 0, minlen = 0;
        for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
            int[] value = entry.getValue();
            if (value[0] > maxnum) {
                maxnum = value[0];
                minlen = value[2] - value[1] + 1;
            } else if (value[0] == maxnum) {
                minlen = Math.min(minlen, value[2] - value[1] + 1);
            }
        }
        return minlen;
    }

    public static void main(String[] args) {
        // [1, 2, 2, 3, 1] answer = 2
        System.out.println(new February20().findShortestSubArray(new int[]{1, 2, 2, 3, 1}));
    }
}
